#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

const int inf = INT_MAX / 2;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  string s, t;
  while (cin >> s >> t) {
    int n = s.size();
    s = ' ' + s;
    t = ' ' + t;

    vector<vector<array<int, 2>>> dp(n + 1, vector<array<int, 2>>(n + 1));
    for (int l = n; l >= 1; l --) {
      for (int r = l; r <= n; r ++) {
        bool same = true;
        bool same_t = true;
        for (int i = l; i <= r; i ++) {
          if (s[i] != t[i]) same = false;
          if (t[i] != t[l]) same_t = false;
        }
        dp[l][r] = {inf, inf};
        if (same) dp[l][r][0] = 0;
        if (same_t) dp[l][r][1] = 1;
          
        for (int k = l; k < r; k ++) {
          dp[l][r][0] = min(dp[l][r][0], min(dp[l][k][0], dp[l][k][1]) + min(dp[k + 1][r][0], dp[k + 1][r][1]));
          dp[l][r][1] = min(dp[l][r][1], dp[l][k][1] + dp[k + 1][r][1]);
        }
        if (t[l] == t[r]) {
          for (int k = l; k < r; k ++) {
            if (t[k] == t[l]) {
              dp[l][r][1] = min(dp[l][r][1], dp[l][k][1] + dp[k + 1][r - 1][1]);
            }
          }
        }
      }
    }
    cout << min(dp[1][n][0], dp[1][n][1]) << endl;
  }
}